SEC 1
楕円曲線の元の仕様
適当に
効率的な暗号化の標準
SEC 1: 楕円曲線暗号
Certicom Research
連絡先: Daniel R. L. Brown (dbrown@certicom.com)
2009年5月21日
Version 2.0
1 はじめに
このセクションでは、この規格の概要、その使用、目的、および開発について説明します。
1.1 概要
この文書は、楕円曲線暗号（ECC）に基づく公開鍵暗号方式を規定する。具体的には、以下の内容を規定する。
署名方式
暗号化および鍵転送方式
鍵共有方式
また、これらの方式を構築するために用いられる暗号プリミティブと、これらの方式を識別するためのASN.1構文についても説明する。
これらの方式は、コンピュータシステムおよび通信システムにおける一般的な応用を目的としている。
1.2 目的
この文書の目的は以下の3つです。
第一に、ECCに基づく効率的で確立され、広く理解されている公開鍵暗号方式を完全に規定することにより、ECCの導入を促進すること。
第二に、ANS X9.62 X9.62a、WAP WTLS WTLS、ANS X9.63 X9.63、IEEE 1363 1363、およびNIST SP 800-56 800-56A勧告などの標準をプロファイリングすることにより、ECCの相互運用可能な実装の導入を促進すること。ただし、これらの標準で認められているオプションを制限することで、相互運用性の可能性を高め、可能な限り多くの標準への適合を確保すること。 第三に、ベースライン技術を明確かつ完全に公開的に規定することにより、暗号学者によるECCの継続的な詳細分析を支援すること。
2 数学的基礎
本節では、楕円曲線暗号に必要な数学的基礎の概要を示します。
本文書で説明する各公開鍵暗号方式の使用には、有限体上の楕円曲線上の算術演算が含まれます。本節では、これらの算術演算を理解し実装するために必要な数学的概念を紹介します。
2.1節では有限体について、2.2節では有限体上の楕円曲線について、2.3節では関連するデータ型とデータ型間の変換に使用される規則について説明します。
実装に関する議論、セキュリティに関する議論、参考文献など、本節の内容に関する解説については、付録Bを参照してください。
抽象的に、有限体は、体元(field elements)と呼ばれるオブジェクトの有限集合(finite set)と、体元のペアに対して実行できる2つの演算（加算と乗算）の記述から構成されます。これらの演算は、特定の性質を持たなければなりません。
q 個の体元を含む有限体が存在する場合と、q が素数のべき乗である場合とで、さらに、そのような q に対してちょうど1つの有限体が存在することがわかります。q 個の体元を含む有限体は $ \mathbb{F}_q と表記されます。
ここでは、2種類の有限体 $ \mathbb{F}_q のみを使用します。1つは、奇数の素数である q = p の有限体 $ \mathbb{F}_p で、素有限体(prime finite fields)と呼ばれます。もう1つは、任意の m ≥ 1 に対して $ q = 2^m の有限体 $ \mathbb{F}_{2^m} で、標数 2 の有限体(characteristic 2 finite fields)と呼ばれます。
ECC に基づく暗号方式を正確に規定するためには、これらの体を具体的に記述する必要があります。セクション 2.1.1 では素有限体について説明し、セクション 2.1.2 では標数 2 の有限体について説明します。
2.1.1 有限体 $ \mathbb{F}_p
有限体 $ \mathbb{F}_p は p 個の元を含む素有限体です。奇数の素数 p に対しては素有限体 $ \mathbb{F}_p は 1 つしか存在しませんが、$ \mathbb{F}_p の元を表す方法は数多くあります。
ここで、$ \mathbb{F}_p の元は整数の集合で表されます。
$ \{0, 1, ... , p - 1\}
加算と乗算は以下のように定義されます。
加算：a, b ∈ $ \mathbb{F}_p ならば、$ \mathbb{F}_p において a + b = r が成り立ちます。ここで、$ r ∈ [0, p − 1] は整数 a + b を p で割ったときの余りです。これは p を法とする加算と呼ばれ、a + b ≡ r (mod p) と書きます。
乗算：a, b ∈ $ \mathbb{F}_p ならば、$ \mathbb{F}_p において ab = s が成り立ちます。ここで、$ s \in [ 0, p − 1] は整数 ab を p で割ったときの余りです。これは p を法とする乗算と呼ばれ、ab ≡ s (mod p) と書きます。
$ \mathbb{F}_pにおける加算と乗算は、通常の整数演算の標準アルゴリズムを用いて効率的に計算できます。 $ \mathbb{F}_pのこの表現において、加法単位元または零元は整数 0 であり、乗法単位元は整数 1 です。
整数の減算と除算を定義するのと同様に、体元の減算と除算を定義するのも簡単です。そのためには、体元の加法逆元（または負の逆元）と乗法逆元を記述する必要があります。
• 加法逆元：$ a \in \mathbb{F}_p の場合、$ \mathbb{F}_p における a の加法逆元 (-a) は、方程式 a + x ≡ 0 (mod p) の唯一の解です。
• 乗法逆元：$ a \in \mathbb{F}_p の場合、a 6 = 0 の場合、$ \mathbb{F}_p における a の乗法逆元 a-1 は、方程式 ax ≡ 1 (mod p) の唯一の解です。
$ \mathbb{F}_p における加法逆元と乗法逆元は効率的に計算できます。乗法逆元は拡張ユークリッド互除法を用いて計算できます。除算と減算は、加法逆数と乗法逆数によって定義されます。a−b mod p は a+(−b) mod p であり、a/b mod p は a(b−1) mod p です。
ここで、使用される素数有限体 $ \mathbb{F}_p は、次の式を満たす必要があります。
$ \lceil log_2p \rceil \in \{192, 224, 256, 384, 521\}
この制約は相互運用性を促進するために設計されており、実装者は、p がワードサイズに整合しているため計算と通信の点で効率的であり、一般的に要求されるすべてのセキュリティレベルを提供できる実装を展開できます。$ \lceil log_2 p\rceil = 512 ではなく $ \lceil log_2 p\rceil = 521 を含めることは、この文書を他の標準化活動、特に米国政府が推奨する楕円曲線ドメインパラメータ 186-2 と整合させるために選択された例外的な方法です。 2.1.2 有限体 $ \mathbb{F}_{2^m}
有限体 $ \mathbb{F}_{2^m}は、$ 2^m 個の元を含む標数 2 の有限体である。m ≥ 1 の 2 のべき乗 $ 2^m に対しては、標数 2 の有限体 $ \mathbb{F}_{2^m} は 1 つしか存在しないが、$ \mathbb{F}_{2^m} の元を表す方法は多数存在する。
ここで、$ \mathbb{F}_{2^m} の元は、次数 m − 1 以下の 2 元多項式の集合で表される。
$ \{a_{m−1}x^{m−1} + a_{m−2}x^{m−2} + · · · + a_1x + a_0 : a_i \in \{0, 1\}\}
加法と乗法は、次式のように、既約な m 次 2 元多項式 $ f (x) （この多項式は縮約多項式と呼ばれる）によって定義される。
加算: $ a = a_{m−1}x^{m−1} + · · · + a_0, b = b_{m−1}x^{m−1} + · · · + b_0 \in \mathbb{F}_{2^m} とすれば、 $ \mathbb{F}_{2^m} において a + b = r が成立する。ただし、 $ r = r_{m−1}x^{m−1} + · · · + r_0 であり、$ r_i ≡ a_i + b_i (\mod 2) とする。
乗算: $ a = a_{m−1}x^{m−1} + · · · + a_0, b = b_{m−1}x^{m−1} + · · · + b_0 \in \mathbb{F}_{2^m} とすれば、 $ \mathbb{F}_{2^m}において ab = s が成立する。ただし、 $ s = s_{m−1}x^{m−1} + · · · + s_0 は、すべての係数演算を 2 を法として実行し、多項式 ab を$ f (x) で割ったときの剰余である。
$ \mathbb{F}_{2^m}における加算と乗算は、通常の整数演算および多項式演算の標準アルゴリズムを使用して効率的に計算できる。 $ \mathbb{F}_{2^m} のこの表現において、加法単位元または零元は多項式 0 であり、乗法単位元は多項式 1 です。
ここでも、体元の減算と除算を定義することが便利です。そのためには、体元の加法逆元（または負の逆元）と乗法逆元を記述する必要があります。
加法逆元： $ a \in \mathbb{F}_{2^m} の場合、 $ \mathbb{F}_{2^m} における a の加法逆元 (-a) は、 $ \mathbb{F}_{2^m} における方程式 a + x = 0 の唯一の解です。すべての $ a \in \mathbb{F}_{2^m} について、-a = a であることに注意してください。
乗法逆元： $ a \in \mathbb{F}_{2^m}の場合、 $ a \ne 0 の場合、 $ \mathbb{F}_{2^m} における a の乗法逆元 $ a^{-1} は、 $ \mathbb{F}_{2^m} における方程式 ax = 1 の唯一の解です。
$ \mathbb{F}_{2^m} の加法逆元と乗法逆元は効率的に計算できます。乗法逆数は、拡張ユークリッド互除法の多項式版を用いて計算できます。
除算と減算は、加法逆数と乗法逆数によって定義されます。$ \mathbb{F}_{2^m} の a − b は $ \mathbb{F}_{2^m} の a + (−b) であり、$ \mathbb{F}_{2^m} の a/b は $ \mathbb{F}_{2^m} の $ a(b^{−1}) です。
ここで、使用される特性2の有限体 $ \mathbb{F}_{2^m} は、以下の式を満たす必要があります。
$ m \in \{163,233,239,283,409,571\}
$ \mathbb{F}_{2^m}での加算と乗算は、表1のm次の既約2進多項式のいずれかを使用して実行する必要があります。これまでと同様に、この制限は相互運用性を促進し、実装者が共通のセキュリティ要件を満たす効率的な実装を展開できるように設計されています。
table:表1: F_2^mの表現
Field Reduction Polynomial(s)
体 縮小多項式
F_2^163 f(x) = x^163 + x^7 + x^6 + x^3 + 1
F_2^233 f(x) = x^233 + x^74 + 1
F_2^239 f(x) = x^239 + x^36 + 1 または x^239 + x^158 + 1
F_2^283 f(x) = x^283 + x^12 + x^7 + x^5 + 1
F_2^409 f(x) = x^409 + x^87 + 1
F_2^571 f(x) = x^571 + x^10 + x^5 + x^2 + 1
許容可能な m を選択する際に用いられた規則は、集合
{160, 224, 256, 384, 512, 1024}
内の各整数区間において、そのような m が存在する場合、その区間において、$ \mathbb{F}_{2^m} 上の素数の 2 倍または 4 倍の位数を持つコブリッツ曲線が存在するという性質を持つ最小の素数 m を選択する、そうでなければ、単にその区間において最小の素数 m を選択するというものである。(コブリッツ曲線とは、a, b ∈ {0, 1} を満たす $ \mathbb{F}_{2^m} 上の楕円曲線である。第 2.2 節を参照。) m = 239 は、既に実務で広く使用されているため、例外的に採用されたものである。m = 277 ではなく m = 283 を採用したのは、この文書を他の標準化活動、特に米国政府が推奨する楕円曲線の領域パラメータ 186-2 と整合させるために、例外的に採用されたものである。合成 m の使用を避けたのは、本仕様を他の標準化活動と整合させ、また m が合成である $ \mathbb{F}_{2^m} 上に定義された楕円曲線のセキュリティについて一部の専門家が表明した懸念に対処するためです (例えば、GS99、JMS01、GHS02、Hes05、MT06 を参照)。 許容可能な約分多項式を選択する際に使用される規則は次のとおりです。
$ f (x) = x^m + x^k + 1 with $ m > k ≥ 1
という m 次二項式が存在する場合は、k が可能な限り小さいこの三項式を使用します。そうでない場合は、
f (x) = xm + xk3 + xk2 + xk1 + 1 (m > k3 > k2 > k1 ≥ 1) という m 次二項式を使用します。
$ f (x) = x^m + x^{k_3} + x^{k_2} + x^{k_1} + 1 with $ m > k_3 > k_2 > k_1 ≥ 1
という条件で、(1) $ k_3 は可能な限り小さい、(2) $ k_3 が与えられた場合の $ k_2 は可能な限り小さい、(3) $ k_3 と $ k_2 が与えられた場合の $ k_1 は可能な限り小さい。これらの多項式は、体演算の効率的な計算を可能にします。m = 239 の2番目の縮約多項式は、広く使用されているため、例外的に選択されました。
2.2 楕円曲線
$ \mathbb{F}_q 上の楕円曲線は、$ \mathbb{F}_q の方程式の解によって定義されます。$ \mathbb{F}_q 上の楕円曲線を定義する方程式の形は、体（$ \mathbb{F}_q が素数有限体か、または標数 2 の有限体か）によって異なります。
2.2.1 節では素数有限体上の楕円曲線について、2.2.2 節では標数 2 の有限体上の楕円曲線について説明します。
2.2.1 $ \mathbb{F}_p 上の楕円曲線
$ \mathbb{F}_p を素有限体とし、$ p を奇素数とする。また、$ a, b \in \mathbb{F}_p は $ 4a^3 +27b^2 \not\equiv 0 (mod p) を満たすものとする。このとき、パラメータ $ a, b \in \mathbb{F}_p によって定義される $ \mathbb{F}_p 上の楕円曲線 $ E(\mathbb{F}_p)は、方程式 $ P = (x, y) の $ x, y \in \mathbb{F}p に対する解の集合、すなわち点 $ P = (x, y) の集合から構成される。
$ y^2 ≡ x^3 + ax + b (\mod p)
そして、無限遠点と呼ばれる追加の点 $ O を伴う。方程式 $ y^2 \equiv x^3 + ax+b (\mod p) は、$ E(\mathbb{F}_p) の定義方程式と呼ばれる。与えられた点 $ P = (x_P , y_P ) に対して、$ x_P は P の x 座標、$ y_P は P の y 座標と呼ばれる。
$ E(\mathbb{F}_p) 上の点の数は $ \#E(\mathbb{F}_p)で表される。ハッセの定理は次のように規定する:
$ p + 1 − 2\sqrt{p} \le \#E(\mathbb{F}_p) \le p + 1 + 2\sqrt{p}
E 上の点を加算する加法則を定義することが可能である。加法則は以下のように規定される:
1. 無限遠点をそれ自身に加える規則:
$ O + O = O
2. 無限遠点を他の任意の点に加える規則:
$ (x,y) + O = O + (x, y) = (x, y) for all $ (x,y) \in E(\mathbb{F}_p)
3. 同じx座標を持つ2点を、異なる点、またはy座標が0の点と加算する規則：
$ (x,y) + (x, -y) = O for all $ (x, y) \in E(\mathbb{F}_p)
-- つまり、点(x, y)の負の数は、-(x, y) = (x, -y)です。
4. 異なるx座標を持つ2点を加算する例: $ (x1, y1) \in E(\mathbb{F}_p)と $ (x2, y2) \in E(\mathbb{F}_p) を、$ x1 \ne x2 となる2点とします。すると、$ (x1, y1) + (x2, y2) = (x3, y3) となります。ここで、
$ x_3 \equiv \lambda^2-x_1-x_2(\mod p), y_3 \equiv \lambda(x_1 - x_3)-y_1 (\mod p), および $ \lambda\equiv \frac{y_2-y_1}{x_2-x_1} (\mod p)
5. 点をそれ自身に加える（点を2倍にする）規則：$ (x_1, y_1) \in E(\mathbb{F}_p) を $ y_1 \ne 0 となる点とします。
すると、$ (x_1, y_1) + (x_1, y_1) = (x_3, y_3) となります。ここで、
$ x_3 \equiv \lambda^2-2x_1(\mod p), y_3 \equiv \lambda(x_1-x_3)-y_1(\mod p), および $ \lambda \equiv \frac{3x_1^2+a}{2y_1}(\mod p)
$ E(\mathbb{F}_p) 上の点の集合は、この加法規則のもとで群を形成します。さらに、この群はアーベル群です。つまり、すべての点 $ P_1, P_2 \in E(\mathbb{F}_p) について、$ P_1 + P_2 = P_2 + P_1 が成り立ちます。加法規則は常に、単純な体算術を用いて効率的に計算できることに注目してください。
ECC に基づく暗号方式は、楕円曲線点のスカラー乗算に依存しています。整数 $ k と点 $ P \in E(\mathbb{F}_p) が与えられたとき、スカラー乗算は $ P をそれ自身に $ k 回加算する処理です。このスカラー乗算の結果は $ kP と表されます。楕円曲線点のスカラー乗算は、加法規則と double-and-add アルゴリズムまたはその派生アルゴリズムのいずれかを用いることで効率的に計算できます。
2.2.2 $ \mathbb{F}_{2^m}上の楕円曲線
2.3 データ型と変換
このドキュメントで規定されているスキームには、複数の異なるデータ型を用いた演算が含まれます。このセクションでは、様々なデータ型を列挙し、あるデータ型を別のデータ型に変換する方法について説明します。
このドキュメントでは、5つのデータ型が用いられています。楕円曲線演算に関連する3つの型（整数(integers)、体元(field elements)、楕円曲線点(elliptic curve points)）に加え、情報の通信と保存に使用されるオクテット列、および一部のプリミティブで使用されるビット列です。
多くの場合、あるデータ型を別のデータ型に変換する必要が生じます。例えば、楕円曲線上の点をオクテット列として表現する場合などです。このセクションの残りの部分では、必要な変換をどのように行うべきかについて説明します。
図1は、必要な変換とその記述箇所を示しています。
図1: データ型間の変換 (略)
2.3.1 ビット列からオクテット列への変換
ビット列は、このセクションで説明するようにオクテット列に変換する必要があります。非公式な考え方としては、ビット列の左側に0を詰めて長さを8の倍数にし、その結果をオクテットに分割します。正式な変換ルーチンは以下のように規定されます。
入力: blenビットのビット列 B
出力: 長さ$ mlen = \lceil blen/8\rceilオクテットのオクテット列 M
処理: ビット列 $ B = B_0B_1...B_{blen-1} からオクテット列$ M = M_0M_1...M_{mlen-1} に変換します
1. For 0 < i <= mlen - 1,
$ M_i = B_{blen - 8 - 8(mlen-1-i)}B_{blen-7-8(mlen-1-i)}...B_{blen-1-8(mlen-1-i)}
2. $ M_0の左端の$ 8(mlen) − blenビットを0にし、右端の$ 8 − (8(mlen) − blen)ビットを$ B_0B_1 . . . B_{8−8(mlen)+blen−1}に設定する。
3. 出力 $ M
2.3.2 オクテット列からビット列への変換
オクテット列は、このセクションで説明するようにビット列に変換する必要があります。非公式には、オクテット列をビット列として扱うという単純な考え方です。公式には、変換ルーチンは以下のように規定されます。
入力: 長さ mlen オクテットのオクテット列 M。
出力: 長さ blen = 8(mlen) ビットのビット列 B。
処理: オクテット列 $ M = M_0M_1 . . . M_{mlen−1} を、以下のようにビット文字列 $ B = B_0B_1 . . . B_{blen−1} に変換します。
1. 0 ≤ i ≤ mlen − 1 に対して、次のように設定します。
$ B_{8i}B_{8i+1} ... B_{8i+7} = M_i
2. 出力 $ B
2.3.3 楕円曲線点からオクテット列への変換
楕円曲線上の点は、この節で説明するようにオクテット列に変換する必要があります。非公式には、点圧縮が使用されている場合、圧縮されたy座標がオクテット文字列の左端オクテットに配置され、点圧縮がオンであることを示す情報も含まれ、x座標がオクテット列の残りの部分に配置されます。点圧縮がオフの場合、左端オクテットは点圧縮がオフであることを示し、オクテット列の残りの部分にはx座標とy座標が含まれます。正式な変換ルーチンは次のように規定されます。
設定: 点を点圧縮を使用して表現するかどうかを決定します。
入力: 体元 a, b によって定義される $ \mathbb{F}_q 上の楕円曲線上の点 $ P。
出力: 長さ mlen オクテットのオクテット列 M。ただし、$ P = O の場合は mlen = 1、$ P \ne O かつ点圧縮が使用されている場合は $ mlen = \lceil (log_2 q)/8\rceil+1、$ P \ne O かつ点圧縮が使用されていない場合は $ mlen = 2\lceil(log_2 q)/8\rceil + 1 です。
処理: 次のように、P をオクテット文字列 $ M = M_0M_1...M_{mlen−1} に変換します。
1. $ P = O の場合は、$ M = 00_{16} を出力します。
2. $ P = (x_P , y_P ) \ne O かつ点圧縮が使用されている場合は、次のように処理します。
2.1. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ x_P を長さ $ \lceil (log_2 q)/8\rceil オクテットのオクテット列 $ X に変換します。
2.2. $ y_P から 1 ビット $ \tilde{y}P を次のように導出します（これにより、y 座標を 1 ビットで簡潔に表現できます）。
2.2.1. $ q = p が奇数の素数の場合、$ \tilde{y}P = yP (\mod 2) とします。
2.2.2. $ q = 2^m の場合、$ x_P = 0 であれば $ \tilde{y}_P = 0 とします。それ以外の場合は、$ z = z_{m−1}x^{m−1} + ... + z_1x + z_0 を計算します。$ z = y_P x_P^{−1} となり、$ \tilde{y}_P = z_0 とします。
2.3. $ \tilde{y}_P = 0の場合は単一オクテット$ Yに値$ 02_{16}を割り当て、$ \tilde{y}_P = 1の場合は値$ 03_{16}を割り当てます。
2.4. 出力 $ M = Y || X
3. $ P = (x_P , y_P ) \ne Oかつポイント圧縮が使用されていない場合は、次の手順に従います。
3.1. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ x_P を長さ $ \lceil (log_2 q)/8\rceil オクテットのオクテット列 $ X に変換します。
3.2. セクション 2.3.5 で指定された変換ルーチンを使用して、体元 $ y_P を長さ $ \lceil (log_2 q)/8\rceil オクテットのオクテット列 $ Y に変換します。
3.3. 出力 $ M = 04_{16} || X || Y
2.3.4 オクテット列から楕円曲線点への変換
オクテット列は、このセクションで説明するように楕円曲線の点に変換する必要があります。非公式な考え方としては、オクテット列が圧縮された点を表す場合、圧縮されたy座標を左端のオクテットから復元し、x座標をオクテット列の残りの部分から復元し、その後、点の圧縮プロセスを逆に実行します。そうでない場合は、オクテット列の左端のオクテットを削除し、残りのオクテット列の左半分からx座標を復元し、残りのオクテット列の右半分からy座標を復元します。形式的には、変換ルーチンは以下のように規定される。
入力: 体元 a, b と、単一のオクテット $ 00_{16}、長さ $ mlen = \lceil (log_2 q)/8\rceil+1 のオクテット文字列、または長さ $ mlen = 2\lceil (log_2 q)/8\rceil+1のオクテット列のいずれかであるオクテット列 $ M で定義される$ \mathbb{F}_q 上の楕円曲線。
出力: 楕円曲線点 $ P 、または「無効」("invalid")。
処理: 以下のように $ M を楕円曲線点 $ P に変換する。
1. $ M = 00_{16} のとき出力 $ P = O
2. $ Mの長さが $ \lceil (log_2 q)/8\rceil+1オクテットの場合、次のように処理します。
2.1. $ M = Y || X を、1 オクテット $ Y とそれに続く $ \lceil (log_2 q)/8\rceil オクテット $ X として解析します。
2.2. セクション 2.3.6 で指定された変換ルーチンを使用して、$ X を $ \mathbb{F}_q の体元 $ x_P に変換します。ルーチンが "invalid" を出力した場合は、"invalid" を出力して停止します。
2.3. $ Y = 02_{16} の場合は $ \tilde{y}P = 0に設定し、$ Y = 03_{16} の場合は $ \tilde{y}P = 1に設定します。それ以外の場合は "invalid" を出力して停止します。
2.4. $ x_P と $ \tilde{y}_P から楕円曲線点 $ P = (x_P , y_P) を導出します。ここで、
2.4.1. q = p が奇数の素数である場合、体元 $ \alpha \equiv x_P^3+ax_P+b(\mod p) を計算し、p を法とする $ \alpha の平方根 $ \beta を計算する。$ p を法とする $ \alpha の平方根がない場合は「invalid」を出力して終了する。それ以外の場合は、 $ \beta \equiv \tilde{y}_P (\mod 2) の場合は $ y_P = \beta とし、$ \beta \not\equiv \tilde{y}P (\mod 2) の場合は $ y_P = p − \beta とする。
2.4.2. $ q = 2^m かつ $ x_P = 0 の場合、$ \mathbb{F}_{2^m} において $ \tilde{y}_P = b^{2^{m-1}} を出力する。
2.4.3. $ q = 2^m かつ$ x_P \ne 0 の場合、$ \mathbb{F}_{2^m} の体元$ \beta = x_P + a + bx_P^{-2} を計算し、$ \mathbb{F}_{2^m} で$ z^2 + z = \beta となるような元 $ z = z_{m−1}x^{m−1} + · · · + z_1x + z_0 を求めます。そのようなzが存在しない場合は「invalid」を出力して停止し、そうでない場合は $ z_0 = \tilde{y}_P の場合は$ \mathbb{F}_{2^m} で$ y_P = x_P z に設定し、$ z_0 \ne \tilde{y}_P の場合は$ \mathbb{F}_{2^m} で $ y_P = x_P (z + 1) に設定します。
2.5. 出力 $ P = (x_P, y_P)
3. $ M の長さが $ 2\lceil (log_2 q)/8\rceil+1 オクテットの場合、次の手順に従います。
3.1. $ M = W || X || Y を、1つのオクテット $ W とそれに続く $ \lceil (log_2 q)/8\rceil オクテット $ X 、それに続く $ \lceil (log_2 q)/8\rceil オクテット $ Y として解析します。
3.2. $ W = 04_{16} であることを確認します。$ W \ne 04_{16} の場合、「invalid」を出力して停止します。
3.3. 2.3.6節で指定された変換ルーチンを用いて、$ X を$ \mathbb{F}_q の体元$ x_P に変換する。ルーチンが「invalid」を出力した場合は「invalid」を出力し、停止する。
3.4. 2.3.6節で指定された変換ルーチンを用いて、$ Y を$ \mathbb{F}_q の体元$ y_P に変換する。ルーチンが「invalid」を出力した場合は「invalid」を出力し、停止する。
3.5. $ P = (x_P , y_P ) が楕円曲線の定義式を満たしていることを確認します。
3.6. 出力 $ P = (x_P, y_P)
2.3.5 フィールド要素からオクテット列への変換
2.3.6 オクテット列からフィールド要素への変換
2.3.7 整数からオクテット列への変換
2.3.8 オクテット列から整数への変換
2.3.9 フィールド要素から整数への変換